Linked List এর বেসিক কনসেপ্ট

Linked List একটি বেসিক ডাটা স্ট্রাকচার যা বিভিন্ন নোড (Node) দিয়ে গঠিত। প্রতিটি নোডে দুটি অংশ থাকে: একটি ডেটা (data) এবং একটি পয়েন্টার (pointer) যা পরবর্তী নোডের ঠিকানা (address) নির্দেশ করে। Linked List গুলি অ্যারে ভিত্তিক ডাটা স্ট্রাকচারগুলির তুলনায় আরো নমনীয় এবং ডাইনামিক (dynamic) হয়, কারণ এতে এলিমেন্ট ইনসার্ট বা ডিলিট করা অনেক সহজ হয়।

এখানে আমরা জাভা দিয়ে Linked List এর মূল ধারণা এবং এর কিভাবে কাজ করে তা জানব।

1. Linked List এর মৌলিক উপাদান

Linked List তে প্রতিটি নোডের দুটি প্রধান উপাদান থাকে:

• Data: নোডে থাকা মূল তথ্য।
• Next (Pointer): পরবর্তী নোডের ঠিকানা (অথবা নোডের রেফারেন্স)।

উদাহরণ:

ধরা যাক, একটি লিঙ্কড লিস্ট যেটি পাঁচটি সংখ্যাকে ধারণ করছে: 10 -> 20 -> 30 -> 40 -> 50। এখানে:

• প্রথম নোডের data হবে 10 এবং next পয়েন্টার দ্বিতীয় নোডে, যার data হবে 20।
• দ্বিতীয় নোডের data হবে 20 এবং next পয়েন্টার তৃতীয় নোডে, এবং এটি চলতে থাকে।

2. Linked List এর ধরণ

Linked List মূলত তিন ধরনের হয়ে থাকে:

• Singly Linked List: এতে প্রতিটি নোডে শুধুমাত্র একটি পয়েন্টার থাকে, যা পরবর্তী নোডকে নির্দেশ করে।
• Doubly Linked List: এতে প্রতিটি নোডে দুটি পয়েন্টার থাকে, একটি পূর্ববর্তী নোডকে এবং আরেকটি পরবর্তী নোডকে নির্দেশ করে।
• Circular Linked List: এতে শেষ নোডের next পয়েন্টার প্রথম নোডের দিকে নির্দেশ করে, ফলে এটি একটি চক্রাকার লিস্ট হয়ে যায়।

3. Singly Linked List এর মৌলিক কনসেপ্ট

Singly Linked List এ প্রতিটি নোডের মধ্যে একটি data এবং একটি next পয়েন্টার থাকে যা পরবর্তী নোডকে নির্দেশ করে। এই পয়েন্টারটি শেষ নোডে null থাকে, যা নির্দেশ করে যে এটি লিস্টের শেষ নোড।

Singly Linked List এর স্ট্রাকচার:

Head -> [Data | Next] -> [Data | Next] -> [Data | Next] -> null

4. Singly Linked List এর অপারেশন

4.1 নতুন নোড ইনসার্ট করা

Linked List-এ নতুন নোড ইনসার্ট করার জন্য মূলত তিনটি পদ্ধতি রয়েছে:

• Head এ ইনসার্ট করা
• Tail (শেষ) এ ইনসার্ট করা
• কোনো নির্দিষ্ট পজিশনে ইনসার্ট করা

উদাহরণ: Head এ নতুন নোড ইনসার্ট করা

class Node {
    int data;
    Node next;

    // Constructor
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // নতুন নোড ইনসার্ট করার মেথড (Head এ)
    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;  // Head এর পরবর্তী নোডটি নতুন নোডের পরবর্তী নোড হবে
        head = newNode;  // নতুন নোডটি এখন Head হয়ে যাবে
    }

    // লিঙ্কড লিস্ট প্রিন্ট করার মেথড
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        
        // Head এ ইনসার্ট করা
        list.insertAtHead(10);
        list.insertAtHead(20);
        list.insertAtHead(30);
        
        // লিস্ট প্রিন্ট করা
        list.printList();  // আউটপুট: 30 -> 20 -> 10 -> null
    }
}

ব্যাখ্যা:

• insertAtHead(int data) মেথড নতুন একটি নোড তৈরি করে এবং তা লিস্টের প্রথমে ইনসার্ট করে।
• printList() মেথডের মাধ্যমে লিস্টের সকল নোড প্রিন্ট করা হয়।

4.2 নোড ডিলিট করা

Linked List থেকে নোড ডিলিট করা সাধারণত দুটি কেসে করা হয়:

• Head নোড ডিলিট করা
• নির্দিষ্ট নোড ডিলিট করা

উদাহরণ: Head নোড ডিলিট করা

class LinkedList {
    Node head;

    // Head নোড ডিলিট করার মেথড
    public void deleteAtHead() {
        if (head != null) {
            head = head.next;  // Head নোডের পরবর্তী নোডকে নতুন Head বানানো
        }
    }

    // লিঙ্কড লিস্ট প্রিন্ট করার মেথড
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        
        // কিছু ইনসার্ট করা
        list.insertAtHead(10);
        list.insertAtHead(20);
        list.insertAtHead(30);
        
        // লিস্ট প্রিন্ট করা
        list.printList();  // আউটপুট: 30 -> 20 -> 10 -> null
        
        // Head নোড ডিলিট করা
        list.deleteAtHead();
        
        // লিস্ট প্রিন্ট করা
        list.printList();  // আউটপুট: 20 -> 10 -> null
    }
}

ব্যাখ্যা:

• deleteAtHead() মেথডটি Head নোডটি ডিলিট করে এবং পরবর্তী নোডটি নতুন Head হয়ে যায়।

5. Linked List এর ফিচার

• Dynamic Memory Allocation: Linked List এর সবচেয়ে বড় সুবিধা হল এটি ডাইনামিক মেমরি এলোকেশন করে, অর্থাৎ এলিমেন্টগুলি ইনসার্ট করার সময় এক্সট্রা মেমরি প্রয়োজন হয় না।
• Efficient Insertion/Deletion: সিংগলি লিঙ্কড লিস্টে নতুন নোড ইনসার্ট বা ডিলিট করা দ্রুত হয়, বিশেষত যখন এটি লিস্টের প্রথমে বা শেষে হয়।
• Random Access নেই: Linked List তে এলিমেন্ট অ্যাক্সেস করার জন্য লিনিয়ার সার্চ করতে হয়, যা অ্যারের তুলনায় ধীর।

Linked List একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা ডাইনামিক এবং নমনীয় হয়। এটি একাধিক অপারেশন যেমন ইনসার্ট, ডিলিট, এবং ট্রাভার্সাল দ্রুত এবং কার্যকরভাবে করতে সাহায্য করে। Java দিয়ে সিংগলি লিঙ্কড লিস্ট তৈরি এবং ব্যবহার করা যায়, এবং এটি ডাটা স্ট্রাকচার এবং অ্যালগরিদম (DSA) শেখার জন্য একটি আদর্শ প্রাথমিক কনসেপ্ট।